In the school bus scheduling problem, the main contributing factor to thecost is the number of buses needed for the operations. However, in the case ofsubcontracting the transportation of pupils, unbalanced tours can increase thecosts significantly as the lengths of some tours can exceed the daily fixeddriving goal and will result in over-hour charges. This paper proposes a MixedInteger Programming (MIP) model and a matching-based heuristic algorithm tosolve the balanced school bus scheduling problem in a multi-school setting. Theheuristic is guaranteed to find the minimum number of buses. The effectivenessof the heuristic algorithm is tested by comparing its solutions with thesolutions obtained from the MIP whenever the MIP could find a good solution.For larger cases where the MIP cannot find a good solution, we illustrate theperformance of the heuristic by showing how it affects the durations of thetours. To illustrate the performance of the MIP and heuristic, we examine 12different problems with different numbers of trips which are all based on tworeal-world problems. A California case study with 54 trips and the HowardCounty Public School System (HCPSS) with 994 trips. The numerical results oftesting our approach indicate that the proposed algorithm can find reasonablesolutions in a significantly shorter time. The balanced solutions of ouralgorithm can save up to 16% of school bus operation costs compared to the bestsolution found from the MIP model after 40 hours. The balancing stage of theheuristic decreases the Standard Deviation of the tour durations by up to 47%.
展开▼
